# Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.
# Note: 1 ≤ k ≤ n ≤ 109.

# Input:
# n: 13   k: 2

# Output:
# 10

# Explanation:
# The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

import math

# wrong result
class Solution_1(object):
    def find(self, row, col, digit, rowCount):
        lowDigitRowCount = 0
        for n in range(0,int(math.floor(digit - 1))):
            lowDigitRowCount += 10 ** n

        print("lowDigitRowCount :", lowDigitRowCount)

        descCount = rowCount - col + 1
        print("descCount :", descCount)

        page = math.floor((descCount + lowDigitRowCount - 1) / lowDigitRowCount)
        print("page :", page)

        result = (col + 1) * (10 ** (digit - 1)) - (10 ** math.floor(digit - 2)) * page
        print("result :", result)

        remain = (descCount + lowDigitRowCount - 1) % lowDigitRowCount
        print("remain :", remain)

        if(remain > 0):
            result += self.find(remain + 1, col, digit - 1, lowDigitRowCount)
            print("result :", result)

        return result

    def findKthNumber(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """

        lgNum = math.log10(n)
        digit = math.floor(lgNum) + 1
        print("digit :", digit)

        lowDigitTotal = (10 ** (digit - 1) - 1)
        print("lowDigitTotal :", lowDigitTotal)

        total = n - lowDigitTotal
        print("total :", total)

        page = math.floor((total + 9) / 10)
        print("page :", page)

        maxIndex = total + math.floor(page * (10 ** (digit - 2)))
        print("maxIndex :", maxIndex)

        if k > maxIndex:
            return int(self.findKthNumber(lowDigitTotal, k - total))
        else:
            rowCount = 0
            for n in range(0, digit):
                rowCount += 10 ** n

            if rowCount == 0:
                rowCount = 1

            print("rowCount :", rowCount)

            row = k % rowCount
            col = math.floor(k / rowCount + 1)

            if row == 0:
                row = rowCount
                col -= 1

            print("row :", row)
            print("col :", col)

            return int(self.find(row, col, digit, rowCount))

#
class Solution_2(object):
    def findKthNumber(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """

        




#test
print("\n", "-----------------------------------------", "\n")

solution = Solution_1()
result = solution.findKthNumber(100, 10)

print("result :", result)

print("\n", "-----------------------------------------", "\n")